package top.minuy.subject.leetcode._677;

/**
 * 实现一个 MapSum 类，支持两个方法，insert 和 sum：
 *
 * MapSum() 初始化 MapSum 对象
 * void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
 * int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/map-sum-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Minuy
 * @time 20:05
 * @date 2021/10/28
 */
public class MapSum {

    // 节点
    class Node{
        // 单词的值，如果是0则不是单词的末尾
        int value;
        // 子节点
        BSTMap<Character, Node> next;

        public Node(int value){
            this.value = value;
            next = new BSTMap<>();
        }

        public Node(){
            this(0);
        }
    }

    Node root;

    public MapSum() {
        root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = root,temp;
        char c;
        for (int i=0;i<key.length();i++){
            c = key.charAt(i); // 一个一个字母去获取
            temp = cur.next.get(c); //查询下一个字母有没有这个
            if (temp == null){//如果没有
                temp = new Node(); // 新建
                cur.next.add(c,temp); // 链接
            }
            cur = temp; // 到下一个去
        }
        cur.value = val; // 到最后赋值
    }

    public int sum(String prefix) {
        Node cur = root,temp;
        char c;
        // 首先找到其末尾，从这里开始才算
        for (int i = 0;i<prefix.length();i++){
            c = prefix.charAt(i);
            temp = cur.next.get(c);
            if (temp == null){
                return 0;
            }
            cur = temp;
        }
        // 从末尾求所有子结点的和
        return matchSum(cur);
    }

    private int matchSum(Node node){
        // 下面的代码完成了这项工作
//        if (node.next.size == 0){
//            return node.value;
//        }

        int sum = node.value;
        for (String key:node.next.keyStringArray()) {
            sum += matchSum(node.next.get(key.charAt(0)));
        }
        return sum;
    }



    /**
     * 映射
     * @param <K>
     * @param <V>
     */
    interface map<K, V> {
        /**
         * 向字典中添加键值对
         *
         * @param key 键
         * @param val 值
         */
        void add(K key, V val);

        /**
         * 删除一个键值对
         *
         * @param key 要被删除的键
         * @return 返回被删除键的值，如若键不存在，返回空
         */
        V remove(K key);

        /**
         * 查询键是否存在
         *
         * @param key 要查询的键
         * @return 此键是否存在
         */
        boolean contains(K key);

        /**
         * 获取一个键的值
         *
         * @param key 键
         * @return 值
         */
        V get(K key);

        /**
         * 修改一个键值对
         *
         * @param key 键
         * @param newVal 值
         */
        void set(K key, V newVal);

        /**
         * 获取字典的大小
         *
         * @return 字典的大小
         */
        int getSize();

        /**
         * 判断字典是否为空
         *
         * @return 字典是否为空
         */
        boolean isEmpty();
    }

    /**
     * 二分搜索树实现的字典
     * @param <K>
     * @param <V>
     */
    class BSTMap<K extends Comparable<K>,V> implements map<K,V> {

        class Node{
            // 键
            public K key;
            // 值
            public V val;
            // 右子树
            public Node right;
            // 左子树
            public Node left;

            /**
             * 初始化一个节点
             * @param key 节点的键
             * @param val 节点的值
             */
            public Node(K key,V val){
                this.key = key;
                this.val = val;
            }
        }

        /**
         * 根节点
         */
        Node root;
        /**
         * 大小
         */
        int size;

        public BSTMap(){
            root = null;
            size = 0;
        }

        /**
         * 根据key获取节点
         * @param root 根节点
         * @param key 要查找的key
         * @return 对应的节点或者null
         */
        private Node getNode(Node root,K key){
            if(root==null){
                return null;
            }

            if(root.key.compareTo(key)>0){
                return getNode(root.left,key);
            }else if (root.key.compareTo(key)<0){
                return getNode(root.right,key);
            }else { // root.key.compareTo(key) == 0
                return root;
            }
        }

        /**
         * 向字典中添加键值对
         *
         * @param key 键
         * @param val 值
         */
        @Override
        public void add(K key, V val) {
            root = add(root,key,val);
        }

        public String[] keyStringArray(){
            String[] array = new String[size];
            int index = 0;
            // 使用队列辅助完成
            LinkedListQueue<Node> queue = new LinkedListQueue<>();
            // 如果根节点不为空，入队
            if(root!=null){
                queue.enqueue(root);
            }
            // 如果队列内不为空，继续遍历
            while (!queue.isEmpty()){
                // 从队列中取出一个元素
                Node cur = queue.dequeue();
                // 访问
                array[index] = cur.key+"";
                index ++;
                //System.out.print(cur.e+" ");
                // 左节点先入队（左节点先处理）
                if(cur.left!=null){
                    queue.enqueue(cur.left);
                }
                // 右节点入队
                if(cur.right!=null){
                    queue.enqueue(cur.right);
                }
            }

            return array;
        }

        public Node add(Node node,K key, V val) {
            if (node == null){
                size++;
                return new Node(key,val);
            }

            if(key.compareTo(node.key)<0){
                node.left = add(node.left,key,val);
            }else if(key.compareTo(node.key)>0){
                node.right = add(node.right,key,val);
            }else {  // key.compareTo(node.key) == 0
                node.val = val;
            }

            return node;
        }

        /**
         * 获取这棵树中的最小值
         * @param node 根节点
         * @return 最小值所在的节点
         */
        private Node getMinimum(Node node){
            if (node == null){
                return null;
            }
            if(node.left ==null){
                return node;
            }else {
                return getMinimum(node.left);
            }
        }

        private Node removeMinimum(Node node){
            if(node == null){
                return null;
            }

            if (node.left == null){
                Node t = node.right;
                node.right = null;
                size--;
                return t;
            }else{
                node.left = removeMinimum(node.left);
            }
            return node;
        }

        /**
         * 删除一个键值对
         *
         * @param key 要被删除的键
         * @return 返回被删除键的值，如若键不存在，返回空
         */
        @Override
        public V remove(K key) {
            Node node = getNode(root,key);
            if (node==null){
                return null;
            }else {
                root = remove(root,key);
                return node.val;
            }
        }

        private Node remove(Node node,K key){
            if(node == null){
                return null;
            }
            if(node.key.compareTo(key)>0){
                return remove(node.left,key);
            }else if(node.key.compareTo(key)<0){
                return remove(node.right,key);
            }else { // node.key.compareTo(key) == 0
                if(node.left == null){
                    Node t = node.right;
                    node.right = null;
                    size--;
                    return t;
                }

                if(node.right == null){
                    Node t = node.left;
                    node.left = null;
                    size--;
                    return t;
                }

                Node minimumNode = getMinimum(node);
                node.right = removeMinimum(node.right);

                minimumNode.left = node.left;
                minimumNode.right = node.right;

                node.right = node.left = null;

                return minimumNode;
            }
        }

        /**
         * 查询键是否存在
         *
         * @param key 要查询的键
         * @return 此键是否存在
         */
        @Override
        public boolean contains(K key) {
            return getNode(root,key)!=null;
        }

        /**
         * 获取一个键的值
         *
         * @param key 键
         * @return 值
         */
        @Override
        public V get(K key) {
            // 当根节点为空的时候返回空，而不是空指针异常
            return getNode(root,key)==null?null:getNode(root,key).val;
        }

        /**
         * 修改一个键值对
         *
         * @param key    键
         * @param newVal 值
         */
        @Override
        public void set(K key, V newVal) {
            Node node = getNode(root,key);
            if(node==null){
                throw new IllegalArgumentException("Set failed. The \""+key.toString()+"\" is not exists.");
            }else {
                node.val = newVal;
            }
        }

        /**
         * 获取字典的大小
         *
         * @return 字典的大小
         */
        @Override
        public int getSize() {
            return size;
        }

        /**
         * 判断字典是否为空
         *
         * @return 字典是否为空
         */
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    }

    interface Queue <E>{
        /**
         * 获取队列的元素个数
         * @return 元素个数
         */
        int getSize();

        /**
         * 判断队列是否为空
         * @return 是否为空
         */
        boolean isEmpty();

        /**
         * 入队，将元素添加到队尾
         * @param e 放入的元素
         */
        void enqueue(E e);

        /**
         * 出队，将元素从队首拿出
         * @return 拿出的元素
         */
        E dequeue();

        /**
         * 获取队首的元素
         * @return 队首的元素
         */
        E getFront();
    }


    class Node1<E> {
        // 储存的元素
        public E e;
        // 下一个节点的引用
        public Node1<E> next;

        /**
         * 创建节点，传入元素和指向下一个节点
         *
         * @param e    节点存储的元素
         * @param next 下一个节点
         */
        public Node1(E e, Node1<E> next) {
            this.e = e;
            this.next = next;
        }

        /**
         * 创建节点，传入元素，下一个节点为空
         *
         * @param e 本节点存储的元素
         */
        public Node1(E e) {
            this(e, null);
        }

        /**
         * 创建一个节点
         */
        public Node1() {
            this(null, null);
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Node : e = ");
            if(e!=null){
                res.append(e.toString());
            }else {
                res.append("null");
            }
            res.append(", next = ");
            if(next!=null){
                res.append(next.toString());
            }else {
                res.append("null");
            }
            return res.toString();
        }
    }

    class LinkedListQueue<A> implements Queue<A> {

        // 链表的头和尾
        private Node1<A> head,tail;
        // 大小
        private int size;

        public LinkedListQueue(){
            size = 0;
            head = null;
            tail = null;
        }

        /**
         * 获取队列的元素个数
         *
         * @return 元素个数
         */
        @Override
        public int getSize() {
            return size;
        }

        /**
         * 判断队列是否为空
         *
         * @return 是否为空
         */
        @Override
        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 入队，将元素添加到队尾
         *
         * @param e 放入的元素
         */
        @Override
        public void enqueue(A e) {
            // if(size == 0){
            if(tail == null){  // 这里判空比较好，有数据一定不为空，这里判空避免了下面的空指针异常
                tail = new Node1<>(e);
                head = tail;
            }else {
                tail.next = new Node1<>(e);
                tail = tail.next;
            }
            size++;
        }

        /**
         * 出队，将元素从队首拿出
         *
         * @return 拿出的元素
         */
        @Override
        public A dequeue() {
            if(head == null){
                throw new IllegalArgumentException("Dequeue failed. Queue is Empty.");
            }

            Node1<A> res = head;
            head = head.next;
            res.next = null; //  释放内存

            // 全部出去了
            if(head == null){
                tail = null;
            }

            size--;

            return res.e;
        }

        /**
         * 获取队首的元素
         *
         * @return 队首的元素
         */
        @Override
        public A getFront() {
            if(head == null){
                throw new IllegalArgumentException("GetFront failed. Queue is Empty.");
            }

            return head.e;
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append(String.format("LinkedListQueue : size = %d\n",getSize()));
            res.append("front [");
            for (Node1<A> cur = head;cur!=null;cur = cur.next){
                res.append(cur.e.toString());
                if(cur.next!=null){
                    res.append(", ");
                }
            }
            res.append("] tail");

            return res.toString();
        }
    }


//    public static void main(String[] args) {
//        MapSum mapSum = new MapSum();
//        mapSum.insert("apple", 3);
//        System.out.println(mapSum.sum("ap"));  // return 3 (apple = 3)
//        mapSum.insert("app", 2);
//        System.out.println(mapSum.sum("ap"));  // return 5 (apple + app = 3 + 2 = 5)
//    }

}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */